package hot;

/**
 * @author lakersUp
 * @Classname
 * @Description
 * @Date 2022/4/3 10:49
 * @Version 1.0
 */
public class Hot494findTargetSumWays {
    public int findTargetSumWays(int[] nums, int s){
        int sum=0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum-s<0 || (sum-s)%2!=0){
            return 0;
        }
        int neg=(sum-s)/2;
        int[][] dp=new int[nums.length+1][neg+1];
        dp[0][0]=1;
        for(int i=1;i<=nums.length;i++){
            for(int j=0;j<=neg;j++){
                if(j>=nums[i-1]){
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
                }else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[nums.length][neg];
    }
}
